第7章 一方向ハッシュ関数

任意長の入力メッセージを元にして固定長のハッシュ値を生成する。ハッシュ値からメッセージを逆算出来ない一方向性(one-way)を持つ。入力は文字列でも画像ファイルでも良い。

入力のメッセージはプレ・イメージ、出力されるハッシュ値はメッセージダイジェストやフィンガープリントとも呼ばれる。

性質

一方向性

衝突耐性

あるメッセージのハッシュ値が与えられた時、そのハッシュ値を持つ別のメッセージを見つけることが非常に困難であることを弱衝突耐性、ハッシュ値が一致するような異なる2つのメッセージを見つけ出すことが非常に困難であることを強衝突耐性という。

使用例

パスワードを元にした暗号化

ファイル改ざん検知

メッセージ認証コード

デジタル署名

擬似乱数生成器

ワンタームパスワード

アルゴリズム

MD4, MD5

Rivestが作った一方向ハッシュ関数で128ビットのハッシュ値を持つ。

衝突耐性は破られており安全ではない。

SHA-1, SHA-256, SHA-386, SHA-512

NIST(National Institute of Standards and Technology)で作られた160ビットのハッシュ値を持つ一方向ハッシュ関数。

SHA-256以降はSHA-2とも言う。

SHA-1の強衝突耐性は破られているので安全ではない。

RIPEMD-160

160ビットのハッシュ値を持つ一方向ハッシュ関数。

RIPEMDの強衝突耐性の強衝突耐性は破られているが、RIPEMD-160はまだ破られていない。

ビットコインで使用されている。

SHA-3

NISTがコンペティションで選定したアルゴリズムKECCAKを採用した一方向ハッシュ関数。

一方向ハッシュ関数への攻撃

ブルートフォースアタック

誕生日攻撃（衝突攻撃）

少なくとも2人の誕生日が一致する確率が1/2以上になるようなグループの人数Nは最低でいくつになるか？

$ N人のうち少なくとも2人の誕生日が一致する確率 = 1 - N人全員の誕生日が一致しない確率

「1年の日数がY日としてN人のグループの少なくとも2人の誕生日が一致する為の最低のNは何か」と考えると、以下の式で表すことができる。

$ N \fallingdotseq \sqrt{Y} (1年の日数の平方根)

$ N \fallingdotseq \sqrt{Y} = \sqrt{2^M} = 2^{m/2}

一方向ハッシュ関数では解決できない問題

なりすまし

認証が必要になる。